﻿#define _CRT_SECURE_NO_WARNINGS 1;
#include <stdio.h>
//习题C++研发 | 数据结构 | 空间复杂度：数据结构2
//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
//假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
//更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
//返回 k。
//int removeelement(int* nums, int numssize, int val) {
//    int arr[100] = { 0 };
//    int count = 0;
//    for (int i = 0; i < numssize; i++)
//    {
//        if (nums[i] != val)
//        {
//            arr[count] = nums[i];
//            count++;
//        }
//    }
//    memcpy(nums, arr, sizeof(int) * count);
//    return count;
//}

//2023-02-23_数组OJ题_作业
// 一:删除排序数组中的重复项
//给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，
//使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
//然后返回 nums 中唯一元素的个数。
//考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//返回 k 。
//int removeDuplicates(int* nums, int numsSize) {
//    int dest = 0;
//    int src = 1;
//    while (src < numsSize)
//    {
//        if (nums[dest] == nums[src])
//        {
//            src++;
//        }
//        else
//        {
//            nums[++dest] = nums[src++];
//        }
//    }
//    return dest + 1;
//}
//二:合并两个有序数组
//给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
//为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//    int end = m + n - 1;
//    int end1 = m - 1;
//    int end2 = n - 1;
//    while ((end1 >= 0) && (end2 >= 0))
//    {
//        if (nums2[end2] > nums1[end1])
//        {
//            nums1[end--] = nums2[end2--];
//        }
//        else
//        {
//            nums1[end--] = nums1[end1--];
//        }
//    }
//    if (end1 < 0)
//    {
//        while (end2 >= 0)
//        {
//            nums1[end--] = nums2[end2--];
//        }
//    }
//}

//给你一个链表的头节点head和一个整数val
//请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//示例 1：
//输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6
//输出：[1, 2, 3, 4, 5]
//示例 2：
//输入：head = [], val = 1
//输出：[]
//示例 3：
//输入：head = [7, 7, 7, 7], val = 7
//输出：[]
  //Definition for singly-linked list.
//  struct listnode {
//      int val;
//      struct listnode *next;
// };
//
//typedef struct listnode listnode;
//listnode* buynewcode(int x)
//{
//    listnode* newcode = (listnode*)malloc(sizeof(listnode));
//    newcode->val = x;
//    newcode->next = null;
//    return newcode;
//}
//void pushback(listnode** pphead, int x)
//{
//    struct listnode* newcode = buynewcode(x);
//    if (*pphead == null)
//    {
//        *pphead = newcode;
//    }
//    else
//    {
//        struct listnode* tail = *pphead;
//        while (tail->next != null)
//        {
//            tail = tail->next;
//        }
//        tail->next = newcode;
//    }
//}
//struct listnode* removeelements(struct listnode* head, int val) {
//    listnode* start = null;
//    if (head == null)
//    {
//        return null;
//    }
//    while (head != null)
//    {
//        if (head->val != val)
//        {
//            pushback(&start, head->val);
//        }
//        head = head->next;
//    }
//    return start;
//}

//2023-02-25_单链表的增删查改等_作业
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* cur = head;
//    struct ListNode* pre = NULL;
//    while (cur)
//    {
//        struct ListNode* next = cur->next;
//        cur->next = pre;
//        pre = cur;
//        cur = next;
//    }
//    return pre;
//}

//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。
//使用快慢指针，快指针一次走两步，慢指针一次走一步
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow, * fast;
//    slow = fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}

//实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
//使用快慢指针，倒数第k个元素和最后一个相距k-1步，则让快指针先走k-1步
//当快指针走到尾部时，慢指针刚好到k的位置
//int kthToLast(struct ListNode* head, int k) {
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//    while (--k)
//    {
//        fast = fast->next;
//    }
//    while (fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return slow->val;
//}

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode dummy = {};
//    struct ListNode* cur = &dummy;
//    while (list1 && list2) {
//        if (list1->val < list2->val) {
//            cur->next = list1;
//            list1 = list1->next;
//        }
//        else {
//            cur->next = list2;
//            list2 = list2->next;
//        }
//        cur = cur->next;
//    }
//    cur->next = list1 ? list1 : list2;
//    return dummy.next;
//}

//单链表的增删查改等
//编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
//ListNode* partition(ListNode* pHead, int x) {
//    ListNode* list2 = NULL, * head2 = NULL;
//    ListNode* list1 = NULL, * head1 = NULL;
//    while (pHead)
//    {
//        if (pHead->val < x)
//        {
//            if (list1 == NULL)
//            {
//                list1 = head1 = pHead;
//                pHead = pHead->next;
//            }
//            else
//            {
//                list1->next = pHead;
//                list1 = list1->next;
//                pHead = pHead->next;
//            }
//        }
//        else
//        {
//            if (list2 == NULL)
//            {
//                list2 = head2 = pHead;
//                pHead = pHead->next;
//            }
//
//            else
//            {
//                list2->next = pHead;
//                list2 = list2->next;
//                pHead = pHead->next;
//            }
//        }
//    }
//    if (list1)
//        list1->next = NULL;//为了防止形成环形链表
//    if (list2)
//        list2->next = NULL;
//    if (head1 == NULL)
//    {
//        return head2;
//    }
//    else {
//        list1->next = head2;
//        return head1;
//    }
//}

//对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//思路：先找到中间节点，然后将后半段进行逆置，依次比较对应位置的值是否相等
//      如果全部相等则返回true，否则返回false(复用了逆置函数和找到中间位置的函数)
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* cur = head;
//    struct ListNode* pre = NULL;
//    while (cur)
//    {
//        struct ListNode* next = cur->next;
//        cur->next = pre;
//        pre = cur;
//        cur = next;
//    }
//    return pre;
//}
//
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow, * fast;
//    slow = fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}
//    bool chkPalindrome(ListNode* head) {
//        ListNode* mid = middleNode(head);
//        ListNode* newhead = reverseList(mid);
//        while (newhead && head)
//        {
//            if (newhead->val == head->val)
//            {
//                newhead = newhead->next;
//                head = head->next;
//            }
//            else
//                return false;;
//        }
//        return true;
//   
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
//思路：先分别遍历一遍两个链表，得到各个链表的长度，再让长链表的头先走差值步，再同时向后走，如果地址相同返回相同地址，否则返回NULL
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* tailA = headA, * tailB = headB;
//    int lenA = 0, lenB = 0;
//    while (tailA)
//    {
//        ++lenA;
//        tailA = tailA->next;
//    }
//    while (tailB)
//    {
//        ++lenB;
//        tailB = tailB->next;
//    }
//    int del = abs(lenA - lenB);
//    struct ListNode* longs = headA;
//    struct ListNode* small = headB;
//    if (lenB > lenA)
//    {
//        longs = headB;
//        small = headA;
//    }
//    while (del--)
//    {
//        longs = longs->next;
//    }
//    while (longs && small)
//    {
//        if (longs == small)
//        {
//            return longs;
//        }
//        longs = longs->next;
//        small = small->next;
//    }
//    return NULL;
//}

//给你一个链表的头节点 head ，判断链表中是否有环。
//思路：创建快慢指针，如果有环则快慢指针会相遇，如果fast或者fast->next指向了NULL说明无环
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}

//单链表OJ
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//struct ListNode* hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//            return fast;
//    }
//    return NULL;
//}
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* meet = (hasCycle(head));
//    if (meet == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* fast = meet;
//    struct ListNode* slow = head;
//    while (1)
//    {
//        if (fast == slow)
//        {
//            return fast;
//        }
//        fast = fast->next;
//        slow = slow->next;
//    }
//}

//.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
// 要求返回这个链表的深度拷贝
//Node* copyRandomList(Node* head) {
//    struct Node* cur = head;
//    while (cur)//创建一个新链表，每个元素在原元素之后
//    {
//        struct Node* next = cur->next;
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//        copy->val = cur->val;
//        copy->next = next;
//        cur->next = copy;
//        cur = next;
//    }
//    cur = head;
//    while (cur)//修改random的指向
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//        if (cur->random == NULL)
//        {
//            copy->random = NULL;
//        }
//        else
//        {
//            copy->random = cur->random->next;
//        }
//        cur = next;
//    }
//    cur = head;
//    struct Node* newhead = NULL;
//    struct Node* newtail = NULL;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//        if (newhead == NULL)
//        {
//            newhead = newtail = copy;
//        }
//        else {
//            newtail->next = copy;
//            newtail = newtail->next;
//        }
//        cur->next = next;
//        cur = next;
//    }
//    return newhead;
//}

//栈的使用
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
//typedef struct stack
//{
//    char* a;
//    int top;
//}ST;
//char match(char a)
//{
//    if (a == ')')
//        return '(';
//    else if (a == ']')
//        return '[';
//    else if (a == '}')
//        return '{';
//    return 0;
//}
//bool isValid(char* s) {
//    char a[10001] = { 0 };
//    ST st = { a,0 };
//    while (*s)
//    {
//        if (*s == '(' || *s == '[' || *s == '{')
//        {
//            st.a[st.top] = *s;
//            st.top++;
//        }
//        else
//        {
//            if (st.top == 0 || match(*s) != st.a[st.top - 1])
//            {
//                return false;
//            }
//            st.top--;
//        }
//        s++;
//    }
//    return st.top == 0;
//}

//队列和栈的OJ
//用队列实现栈
// 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
//实现 MyStack 类：
//void push(int x) 将元素 x 压入栈顶。
//int pop() 移除并返回栈顶元素。
//int top() 返回栈顶元素。
//boolean empty() 如果栈是空的，返回 true ；否则，返回 false 
//注意：
//你只能使用队列的标准操作 —— 也就是 push to back、peek / pop from front、size 和 is empty 这些操作。
//你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
//typedef int QDatatype;
//typedef struct QNode
//{
//	struct QNode* next;
//	QDatatype data;
//}QNode;
//typedef struct Queue
//{
//	QNode* head;
//	QNode* tail;
//	QDatatype size;
//}Queue;
//void QueueInit(Queue* pq)
//{
//	assert(pq);
//	pq->head = NULL;
//	pq->tail = NULL;
//	pq->size = 0;
//}
//void QueueDestroy(Queue* pq)
//{
//	assert(pq);
//	QNode* cur = pq->head;
//	while (cur)
//	{
//		QNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	pq->head = pq->tail = NULL;
//	pq->size = 0;
//}
//
//void QueuePush(Queue* pq, QDatatype x)
//{
//	assert(pq);
//	QNode* newcode = (QNode*)malloc(sizeof(QNode));
//	if (newcode == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//	newcode->data = x;
//	newcode->next = NULL;
//	if (pq->head == NULL)
//	{
//		assert(pq->tail == NULL);
//		pq->head = pq->tail = newcode;
//	}
//	else
//	{
//		pq->tail->next = newcode;
//		pq->tail = newcode;
//	}
//	pq->size++;
//}
//
//void QueuePop(Queue* pq)
//{
//	assert(pq);
//	assert(pq->head != NULL);
//	QNode* next = pq->head->next;
//	free(pq->head);
//	pq->head = next;
//	if (pq->head == NULL)
//	{
//		pq->tail = NULL;
//	}
//	pq->size--;
//}
//
//int QueueSize(Queue* pq)
//{
//	assert(pq);
//	return pq->size;
//}
//
//bool QueueEmpty(Queue* pq)
//{
//	assert(pq);
//	return pq->size == 0;
//}
//
//QDatatype QueueFront(Queue* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//	return pq->head->data;
//}
//
//QDatatype QueueBack(Queue* pq)
//{
//	assert(pq);
//	assert(!QueueEmpty(pq));
//	return pq->tail->data;
//}
//typedef struct {
//	Queue q1;
//	Queue q2;
//} MyStack;
//
//MyStack* myStackCreate() {
//	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
//	if (st == NULL)
//	{
//		perror("Malloc fail");
//	}
//	QueueInit(&st->q1);
//	QueueInit(&st->q2);
//	return st;
//}
//
//void myStackPush(MyStack* obj, int x) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		QueuePush(&obj->q1, x);
//	}
//	else
//	{
//		QueuePush(&obj->q2, x);
//	}
//}
//
//int myStackPop(MyStack* obj) {
//	Queue* empty = &obj->q1;
//	Queue* noempty = &obj->q2;
//	if (!QueueEmpty(&obj->q1))
//	{
//		noempty = &obj->q1;
//		empty = &obj->q2;
//	}
//	while (QueueSize(noempty) > 1)
//	{
//		QueuePush(empty, QueueFront(noempty));
//		QueuePop(noempty);
//	}
//	int top = QueueFront(noempty);
//	QueuePop(noempty);
//	return top;
//}
//
//int myStackTop(MyStack* obj) {
//	if (!QueueEmpty(&obj->q1))
//	{
//		return QueueBack(&obj->q1);
//	}
//	else {
//		return QueueBack(&obj->q2);
//	}
//}
//
//bool myStackEmpty(MyStack* obj) {
//	return (QueueEmpty(&obj->q1)) && (QueueEmpty(&obj->q2));
//}
//
//void myStackFree(MyStack* obj) {
//	QueueDestroy(&obj->q1);
//	QueueDestroy(&obj->q2);
//	free(obj);
//}
//
///**
// * Your MyStack struct will be instantiated and called as such:
// * MyStack* obj = myStackCreate();
// * myStackPush(obj, x);
//
// * int param_2 = myStackPop(obj);
//
// * int param_3 = myStackTop(obj);
//
// * bool param_4 = myStackEmpty(obj);
//
// * myStackFree(obj);
//*/

//用栈实现队列
// 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//实现 MyQueue 类：
//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素
//boolean empty() 如果队列为空，返回 true ；否则，返回 false
//说明：
//你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek / pop from top, size, 和 is empty 操作是合法的。
//你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
//typedef int STDataType;
//typedef struct stack
//{
//	int* a;
//	int top;
//	int capacity;
//}ST;
//
//void STInit(ST* ps)
//{
//	assert(ps);
//	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
//	if (ps->a == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//	ps->capacity = 4;
//	ps->top = 0;//top为栈顶元素的下一个位置
//}
//
//void STDestroy(ST* ps)
//{
//	assert(ps);
//	free(ps->a);
//	ps->a = NULL;
//	ps->top = 0;
//	ps->capacity = 0;
//}
//
//void STPush(ST* ps, STDataType x)
//{
//	assert(ps);
//	if (ps->top == ps->capacity)
//	{
//		STDataType* tem = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
//		if (tem == NULL)
//		{
//			perror("realloc fail");
//			return;
//		}
//		ps->a = tem;
//		ps->capacity = ps->capacity * 2;
//	}
//	ps->a[ps->top] = x;
//	ps->top++;
//}
//bool STEmpty(ST* ps)
//{
//	assert(ps);
//	return ps->top == 0;
//}
//void STPop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//	ps->top--;
//}
//
//int STSize(ST* ps)
//{
//	assert(ps);
//	return ps->top;
//}
//STDataType STTop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//	return ps->a[ps->top - 1];
//}
//
//typedef struct {
//	ST pushst;
//	ST popst;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//	MyQueue* Que = (MyQueue*)malloc(sizeof(MyQueue));
//	if (Que == NULL)
//	{
//		perror("Malloc fail");
//		return NULL;
//	}
//	STInit(&Que->pushst);
//	STInit(&Que->popst);
//	return Que;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//	STPush(&obj->pushst, x);
//}
//
//int myQueuePop(MyQueue* obj) {
//	if (STEmpty(&obj->popst))
//	{
//		while (!STEmpty(&obj->pushst))
//		{
//			STPush(&obj->popst, STTop(&obj->pushst));
//			STPop(&obj->pushst);
//		}
//	}
//	int front = STTop(&obj->popst);
//	STPop(&obj->popst);
//	return front;
//}
//
//int myQueuePeek(MyQueue* obj) {
//	if (STEmpty(&obj->popst))
//	{
//		while (!STEmpty(&obj->pushst))
//		{
//			STPush(&obj->popst, STTop(&obj->pushst));
//			STPop(&obj->pushst);
//		}
//	}
//	int front = STTop(&obj->popst);
//	return front;
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
//}
//
//void myQueueFree(MyQueue* obj) {
//	STDestroy(&obj->pushst);
//	STDestroy(&obj->popst);
//	free(obj);
//}
//
///**
// * Your MyQueue struct will be instantiated and called as such:
// * MyQueue* obj = myQueueCreate();
// * myQueuePush(obj, x);
//
// * int param_2 = myQueuePop(obj);
//
// * int param_3 = myQueuePeek(obj);
//
// * bool param_4 = myQueueEmpty(obj);
//
// * myQueueFree(obj);
//*/

//队列与二叉树
//设计你的循环队列实现。 循环队列是一种线性数据结构，
//其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
//循环队列的一个好处是我们可以利用这个队列之前用过的空间。
//在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
//但是使用循环队列，我们能使用这些空间去存储新的值。
//你的实现应该支持如下操作：
//MyCircularQueue(k) : 构造器，设置队列长度为 k 。
//Front : 从队首获取元素。如果队列为空，返回 - 1 。
//Rear : 获取队尾元素。如果队列为空，返回 - 1 。
//enQueue(value) : 向循环队列插入一个元素。如果成功插入则返回真。
//deQueue() : 从循环队列中删除一个元素。如果成功删除则返回真。
//isEmpty() : 检查循环队列是否为空。
//isFull() : 检查循环队列是否已满。
//typedef struct {
//    int* a;
//    int front;
//    int rear;
//    int k;
//} MyCircularQueue;
//
//
//MyCircularQueue* myCircularQueueCreate(int k) {
//    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//    obj->front = obj->rear = 0;
//    obj->k = k;
//    obj->a = (int*)malloc(sizeof(int) * (k + 1));
//    return obj;
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj) {
//    return (obj->rear + 1) % (obj->k + 1) == obj->front;
//}
//bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//    return obj->front == obj->rear;
//}
//
//
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//    if (myCircularQueueIsFull(obj))
//    {
//        return false;
//    }
//    obj->a[obj->rear] = value;
//    obj->rear = (obj->rear + 1) % (obj->k + 1);
//    return true;
//}
//
//bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//    if (myCircularQueueIsEmpty(obj))
//        return false;
//    else
//        obj->front = (obj->front + 1) % (obj->k + 1);
//    return true;
//}
//
//int myCircularQueueFront(MyCircularQueue* obj) {
//    if (myCircularQueueIsEmpty(obj))
//    {
//        return -1;
//    }
//    return obj->a[obj->front];
//}
//
//int myCircularQueueRear(MyCircularQueue* obj) {
//    if (myCircularQueueIsEmpty(obj))
//    {
//        return -1;
//    }
//    return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
//}
//
//void myCircularQueueFree(MyCircularQueue* obj) {
//    free(obj->a);
//    free(obj);
//}

//二叉树
//如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
//只有给定的树是单值二叉树时，才返回 true；否则返回 false。
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//
//    if (root->left && root->left->val != root->val)
//        return false;
//
//    if (root->right && root->right->val != root->val)
//        return false;
//
//    return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

//二叉树OJ
// 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
//只有给定的树是单值二叉树时，才返回 true；否则返回 false。
//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//    else if (root->left != NULL && root->left->val != root->val)
//        return false;
//    else if (root->right != NULL && root->right->val != root->val)
//        return false;
//    else
//        return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

//给定一个二叉树 root ，返回其最大深度。
//二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//        return 0;
//    else
//    {
//        int leftheight = maxDepth(root->left);
//        int rightheight = maxDepth(root->right);
//        if (leftheight > rightheight)
//            return leftheight + 1;
//        else
//            return rightheight + 1;
//    }
//}

//给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点
//思路：先将root的左右子节点调换位置，此时左右子节点的子节点还没有进行调换，则再对每一个子节点重复进行调换
//      当这个root为空或者这个root的两个子节点均为空，则停止调换，当所有调换都停止时，翻转完成
//void TreeChange(struct TreeNode* root)
//{
//    if (root == NULL)
//        return;
//    struct TreeNode* left = root->left;
//    struct TreeNode* right = root->right;
//    if (left != NULL || right != NULL)
//    {
//        root->left = right;
//        root->right = left;
//        TreeChange(root->left);
//        TreeChange(root->right);
//    }
//    else
//        return;
//}
//struct TreeNode* invertTree(struct TreeNode* root) {
//    if (root == NULL)
//        return NULL;
//    TreeChange(root);
//    return root;
//}
//
//给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
//如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    else if (p == NULL || q == NULL)
//        return false;
//    else if (p->val != q->val)
//        return false;
//    else
//        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}

//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
//typedef struct TreeNode BTNode;
//int TreeSize(BTNode* root)//求二叉树节点个数
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    else
//    {
//        return TreeSize(root->left) + TreeSize(root->right) + 1;
//    }
//}
//void Preorder(BTNode* root, int* a, int* pi)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    a[(*pi)++] = root->val;
//    Preorder(root->left, a, pi);
//    Preorder(root->right, a, pi);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = TreeSize(root);
//    int* a = (int*)malloc(*returnSize * sizeof(int));
//    int i = 0;
//    Preorder(root, a, &i);
//    return a;
//}

//给你一个二叉树的根节点 root ， 检查它是否轴对称。
//bool Same(struct TreeNode* left, struct TreeNode* right)
//{
//    if (left == NULL && right == NULL)
//        return true;
//    if (left == NULL || right == NULL)
//        return false;
//    if (left->val != right->val)
//        return false;
//    return Same(left->left, right->right) && Same(left->right, right->left);
//}
//bool isSymmetric(struct TreeNode* root) {
//    return Same(root->left, root->right);
//}

//给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
// 如果存在，返回 true ；否则，返回 false 。
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//
//    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL)
//        return false;
//    if (isSameTree(root, subRoot))
//        return true;
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}